package _interview75;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 901. 股票价格跨度
 */
public class No901 {
    private final List<Integer> list;
    private final Deque<Integer> stack;
    private int index = 0;

    public No901() {
        list = new ArrayList<>();
        stack = new ArrayDeque<>();
    }

    public int next(int price) {
        list.add(price);
        while (!stack.isEmpty() && price >= list.get(stack.peek())) {
            stack.pop();
        }
        int ans = stack.isEmpty() ? index + 1 : index - stack.peek();
        stack.push(index++);
        return ans;
    }
}
